洛谷题解 P2872 【[USACO07DEC]道路建设Building Roads】

发表于 | 阅读次数：
本文字数： 2.3k | 阅读时长 ≈ 2 分钟

道路建设

题意：

给你$n$个农场的坐标，给出$m$条已经存在的路（连接农场$i$与农场$j$），求最少要修建多长的路才能把所有农场连接起来。

上面的太啰嗦了，再简化一下：

给你$n$个节点，给出$m$条权值为0的边，每个节点彼此有一条边连接，边权值为两点的欧几里得距离，求该图的最小生成树大小。

欧几里得距离公式：$dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

这道题我是用$Prim$做的，感觉$Prim$更好些，1000个点100条边算稀疏图吧

一定要注意在计算欧几里得距离时要在$sqrt()$里加double，不然就会卡精度WA2个点 （别问我怎么知道的）

代码解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#define INF 20000000 //题中给出的没有那么大，但是开大点不会错
using namespace std;

struct edge
{
	double w;//边权
	int v;//终点
};

vector<edge> G[1010];//动态数组存边

int n,m,zb[1010][3],head;
bool pd[1010][1010],vis[1010];
double ans=0,f[1010];

double dis(int xa,int ya,int xb,int yb)//求欧几里得距离
{
	return sqrt((double)(xa-xb)*(xa-xb)+(double)(ya-yb)*(ya-yb));//注意此处的两个double，被卡WA了两次
}


int main()
{
	scanf("%d%d",&n,&m);
	for(int a=1;a<=n;a++)
	{
		scanf("%d%d",&zb[a][1],&zb[a][2]);//读入坐标
	}
	for(int a=1;a<=m;a++)//标记0权边
	{
		int x,y;
		scanf("%d%d",&x,&y);
		pd[x][y]=true;
		pd[y][x]=true;
	}
	for(int a=1;a<=n;a++)
	{
		for(int b=1;b<=n;b++)
		{
			if(a==b)
			{
				continue;
			}
			else
			{
				edge cmp;
				cmp.v=b;
				if(pd[a][b]==true)//如果被标记边权为0
				{
					cmp.w=0;
				}
				else
				{
					cmp.w=dis(zb[a][1],zb[a][2],zb[b][1],zb[b][2]);
				}
				G[a].push_back(cmp);//存边
			}
		}
	}
	for(int a=1;a<=n;a++)//初始化，赋极值
	{
		f[a]=INF;
	}
   //下方为Prim部分
	for(int a=0;a<G[1].size();a++)//预处理
	{
		int v=G[1][a].v;
		double w=G[1][a].w;
		f[v]=min(f[v],w);
	}
	vis[1]=true;//标记该节点已在最小生成树中
	for(int i=1;i<=n-1;i++)//n个节点，当然n-1条边
	{
		int V;
		double W=INF;//赋极值
		for(int j=1;j<=n;j++)
		{
			if(vis[j])
			{
				continue;
			}
			if(f[j]<W)
			{
				W=f[j];
				V=j;
			}
		}
		ans=ans+W;//统计最小生成树大小
		vis[V]=true;//标记该节点已在最小生成树中
		for(int a=0;a<G[V].size();a++)
		{
			int v=G[V][a].v;
			double w=G[V][a].w;
			f[v]=min(f[v],w);
		}
	}
	printf("%.2lf\n",ans);//输出
	return 0;//好习惯
}

题目详见:https://www.luogu.org/problemnew/show/P2872